Wireless telephony uses messaging for several purposes including, for example, conveying status information, reconfiguring operating modes, handling call termination, and conveying system and user data such as a subscriber's electronic serial number and telephone number, as well as conversations and other data transmitted by the user. Unlike ordinary wire telephony, in which a central serving station is connected to each subscriber by wire, thus ensuring a fair degree of protection from eavesdropping and tampering by an unauthorized party (attacker), wireless telephone serving stations (i.e., base stations) must transmit and receive messages via signals over the air, regardless of the physical location of the subscribers.
Because the base station must be able to send and receive messages to and from a subscriber anywhere, the messaging process is wholly dependent on signals received from and sent to the subscriber equipment. Because the signals are transmitted over the air, they can be intercepted by an eavesdropper or interloper with the right equipment.
If a signal is transmitted by a wireless telephone in plaintext, a danger exists that an eavesdropper will intercept the signal and use it to impersonate a subscriber, or to intercept private data transmitted by the user. Such private data may include the content of conversations. Private data may also include non-voice data transmitted by the user such as, for example, computer data transmitted over a modem connected to the wireless telephone, and may also include bank account or other private user information transmitted typically by means of keypresses. An eavesdropper listening to a conversation or intercepting non-voice data may obtain private information from the user. The message content of an unencrypted telephone signal (i.e., plaintext signal) is relatively easily intercepted by a suitably adapted receiver.
Alternatively, an interloper can interject himself into an established connection by using a greater transmitting power, sending signals to the base station, and impersonating a party to the conversation.
In the absence of applying cryptography to messages being transmitted by wireless signals, unauthorized use of telephone resources, eavesdropping of messages, and impersonation of called or calling parties during a conversation are possible. Such unauthorized interloping and/or eavesdropping has in fact proven to be a grave problem and is highly undesirable.
The application of cryptography to wireless telephone applications offers a solution to the security problems discussed above, but the application of standard cryptography methods to wireless telephony has encountered significant difficulties due to the computationally-intensive nature of these methods. Specifically, these methods are subject to the constraints imposed by the desire to furnish a small wireless handset and the constraints on processing power imposed by the small size of the handset. The processing power present in typical wireless handsets is insufficient to handle the processing requirements of commonly known cryptographic algorithms such as DES (Data Encryption Standard). Implementing such a commonly known cryptographic algorithm in a typical wireless telephone system would potentially increase the time needed to process signals (i.e., encrypt and decrypt), thereby causing unacceptable delays for subscribers.
One cryptographic system for wireless telephony is disclosed in Reeds U.S. Pat. No. 5,159,634 (“Reeds”), incorporated herein by reference. Reeds describes a cryptographic process known as the CMEA (“Cellular Message Encryption Algorithm”) process. Central to the operation of the CMEA is the tbox function, which is a one to one mapping of one octet to another, using a known table and a secret key. Beginning with an initial index, key material is combined with table material in multiple iterations to perform the mapping. The tbox function can be implemented either as a function call or as a static memory-resident tbox table. The tbox table's purpose, when implemented as in the latter case, is to allow significant speed-up of encryption for a given security level.
Enhancements to the CMEA function exist, disclosed in our patent application Ser. No. 09/059,107, now issued patent U.S. Pat. No. 6,266,411, entitled “Methods and Apparatus for Multiple-Iteration filed on Apr. 13, 1998, and our patent application Ser. No. PCT/US98/07404, entitled “Methods and Apparatus For Enhanced Security Expansion of a Secret Key Into a Lookup Table” filed on Apr. 13, 1998. These enhancements provide significantly increased security to the CMEA process. However, additional enhancements would provide further increased security.
The CMEA algorithm of the prior art may be significantly improved as described in greater detail below. These improvements provide an additional degree of security which is highly advantageous.